/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:04
 * Description: 堆排序
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 * https://blog.fundodoo.com/2018/08/29/573.html
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:04
 * @since 1.0.0
 */
public class HeapSort {

    public static void heapSort(int[] list){
        int length = list.length;

        //将无序堆构造一个大根堆，大根堆有length/2个父节点
        for(int i = length/2 - 1;i >= 0;i--){
            headAdjust(list,i,length);
        }

        //逐步将每个最大的根节点和末尾元素交换，并且再调整其为大根堆
        for(int i = length -1; i > 0;i--){
            swap(list,0,i);
            headAdjust(list,0,i);
        }
    }

    public static void headAdjust(int[] list ,int parent,int length){
        //保存当前父节点
        int temp = list[parent];

        //得到左孩子节点
        int leftChild = 2 * parent +1;

        while (leftChild < length){
            //如果parent有右孩子，则判断左孩子是否小于优孩子
            if(leftChild + 1 < length && list[leftChild] < list[leftChild + 1]){
                leftChild ++ ;
            }
            //父节点大于子节点则不交换
            if (temp >= list[leftChild]){
                break;
            }
            //将较大子节点的值赋给父节点
            list[parent] = list[leftChild];
            //然后将子节点作为父节点
            parent = leftChild;
            //找到该父节点较小的左孩子节点
            leftChild = 2 * parent + 1;
        }
        //将temp值赋给较大的子节点，形成两值交换
        list[parent] = temp;
    }

    //交换数组里两个元素的位置
    public static void swap(int[] list , int top ,int last){
        int temp = list[top];
        list[top]  = list[last];
        list[last] = temp;
    }
}
